#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//struct ListNode {
//    int val;
//    struct ListNode* next;
//}; 
//
//class Partition {
//public:
//    ListNode* partition(ListNode* pHead, int x) {
//        // write code here
//        ListNode* p1 = (ListNode*)malloc(sizeof(ListNode));
//        ListNode* p2 = (ListNode*)malloc(sizeof(ListNode));
//        ListNode* pp1 = p1;
//        ListNode* pp2 = p2;
//        ListNode* p = pHead;
//        while (p)
//        {
//            if (p->val < x)
//            {
//                pp1->next = p;
//                p = p->next;
//                pp1 = pp1->next;
//            }
//            else
//            {
//                pp2->next = p;
//                p = p->next;
//                pp2 = pp2->next;
//            }
//        }
//        pp2->next = NULL;
//        pp1->next = p2->next;
//        ListNode* p3 = p1->next;
//        free(p1);
//        free(p2);
//        return p3;
//    }
//};
//
//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
//{
//    if (headA == NULL || headB == NULL)
//    {
//        return NULL;
//    }
//    struct ListNode* curA = headA;
//    struct ListNode* curB = headB;
//    int A = 0;
//    int B = 0;
//    while (curA->next)
//    {
//        A++;
//        curA = curA->next;
//    }
//    while (curB->next)
//    {
//        B++;
//        curB = curB->next;
//    }
//    if (curA != curB)
//    {
//        return NULL;
//    }
//    int C = abs(A - B);
//    curA = headA;
//    curB = headB;
//    if (A > B)
//    {
//        while (C--)
//        {
//            curA = curA->next;
//        }
//    }
//    else
//    {
//        while (C--)
//        {
//            curB = curB->next;
//        }
//    }
//    while (curA != curB)
//    {
//        curA = curA->next;
//        curB = curB->next;
//    }
//    return curB;
//}
//
//bool hasCycle(struct ListNode* head) {
//    struct ListNode* p1 = head;
//    struct ListNode* p2 = head;
//    while (p2 && p2->next)
//    {
//        p2 = p2->next;
//        p2 = p2->next;
//        p1 = p1->next;
//        if (p1 == p2)
//        {
//            return true;
//        }
//    }
//    return false;
//}
//
//struct ListNode* detectCycle(struct ListNode* head)
//{
//    struct ListNode* curA = head;
//    struct ListNode* curB = head;
//    while (curA && curA->next)
//    {
//        curA = curA->next;
//        curA = curA->next;
//        curB = curB->next;
//        if (curA == curB)
//        {
//            curA = head;
//            while (curA != curB)
//            {
//                curA = curA->next;
//                curB = curB->next;
//            }
//            return curA;
//        }
//    }
//    return NULL;
//}

struct Node {
    int val;
    struct Node *next;
    struct Node *random;
};
 
struct Node* copyRandomList(struct Node* head)
{
    if (head == NULL)
    {
        return NULL;
    }
    struct Node* p = head;
    while (p)
    {
        struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
        newnode->val = p->val;
        newnode->random = p->random;
        struct Node* pnext = p->next;
        p->next = newnode;
        newnode->next = pnext;
        p = pnext;
    }
    p = head;
    struct Node* pnew = p->next;
    while (pnew)
    {
        if (pnew->random)
        {
            pnew->random = p->random->next;
        }
        p = pnew->next;
        if (p == NULL)
        {
            break;
        }
        pnew = p->next;
    }
    p = head;
    struct Node* newhead = p->next;
    pnew = p->next;
    while (pnew)
    {
        p->next = pnew->next;
        p = p->next;
        if (p == NULL)
        {
            break;
        }
        pnew->next = p->next;
        pnew = pnew->next;
    }
    return newhead;
}

void Print(struct Node* head)
{
    while (head)
    {
        printf("%d->", head->val);
        head = head->next;
    }
    printf("NULL\n");
}

void Printrandom(struct Node* head)
{
    while (head)
    {
        if (head->random == NULL)
        {
            printf("NULL->");
        }
        else
        {
            printf("%d->", head->random->val);
        }
        head = head->next;
    }
    printf("NULL\n");
}

int main()
{
    struct Node* p1 = (struct Node*)malloc(sizeof(struct Node));
    struct Node* p2 = (struct Node*)malloc(sizeof(struct Node));
    struct Node* p3 = (struct Node*)malloc(sizeof(struct Node));
    struct Node* p4 = (struct Node*)malloc(sizeof(struct Node));
    struct Node* p5 = (struct Node*)malloc(sizeof(struct Node));
    p1->next = p2;
    p1->random = NULL;
    p1->val = 7;
    p2->next = p3;
    p2->random = p1;
    p2->val = 13;
    p3->next = p4;
    p3->random = p5;
    p3->val = 11;
    p4->next = p5;
    p4->random = p3;
    p4->val = 10;
    p5->next = NULL;
    p5->random = p1;
    p5->val = 1;
    Print(p1);
    Printrandom(p1);
    struct Node* p = copyRandomList(p1);
    Print(p1);
    Printrandom(p1);
    return 0;
}